# coding: utf8
# datetime: 2021-04-16
# 题目地址: https://leetcode-cn.com/problems/scramble-string

class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        def dfs(i1: int, i2: int, length: int) -> bool:
            subStr1 = s1[i1:i1+length]
            subStr2 = s2[i2:i2+length]
            # 截取子串相同
            if subStr1 == subStr2:
                return True
            # 字符数量是否相等
            for ch in subStr1:
                if subStr1.count(ch) != subStr2.count(ch):
                    return False
            # 枚举其他分割情况
            for i in range(1, length):
                # 不交换
                if dfs(i1, i2, i) and dfs(i1+i, i2+i, length-i):
                    return True
                # 交换
                if dfs(i1, i2+length-i, i) and dfs(i1+i, i2, length-i):
                    return True

        return dfs(0, 0, len(s1))


a = Solution()
print(a.isScramble("great", "rgeat"))